Binary Search in C

    Binary search is a search algorithm to find the position of an element in a sorted array. It is called a binary search because in order to search the value, it divides the array into two parts.

    What is Binary Search?

    It is a search algorithm that can only be applied to a sorted array. If the elements of an array are not sorted, you need to sort them first using the sort algorithm.

    We can implement binary search using two methods:

    1. Iterative Method
    2. Recursive Method

    Binary Search Working

    In binary search, we first find the middle element of the array by dividing it into two parts (lower half array and upper half array) and then compare it with our target element.

    • If the target element is equal to the middle element of the array, we return the element position plus one because elements stored in the array use indexing, which starts from 0.
    • If the target element is smaller than the middle element, then we again divide the lower half array into two parts and compare the middle element with the target element. We will continue to do this process until the middle element is found equal to the target element.
    • If the target element is larger than the middle element, then we again divide the upper half array into two parts and compare the middle element with the target element. We will continue to do this process until the middle element is found to be equal to the target element.

    In programming, we can perform the repetitive action by using two tools, which are iteration and recursion. In iteration, we use loops such as for, while, and do-while; in recursion, we use the recursion function.

    Binary Search Time & Space Complexities

    Time Complexity

    • Best Case Complexity: O(1)
    • Average Case Complexity: O(log n)
    • Worst Case: O(log n)

    Space Complexity

    The space complexity of binary search is O(1).

    Advantages of Binary Search

    • It uses the divide-and-conquer technique.
    • It is faster than a linear search.
    • Already present in many libraries.
    • Easy to implement.

    Disadvantages of Binary Search

    • Binary search does not adapt well to dynamic datasets where the elements frequently change.
    • It can be tricky for beginners.
    • If elements are added or removed frequently, the entire dataset needs to be re-sorted.

    Applications of Binary Search

    • Java, .Net, C++, and STL libraries.
    • In debugging , binary search points out the position where the error occurs.

    Binary Search in C

    Here, we have provided a binary search program in C using iterators and recursion:

    C Iterative Binary Search

    In iterative binary search, we will use a while loop: 

    #include <stdio.h>
#include<conio.h>
int main()
{
   int i, f, l, mid, num, tar, arr[100];
   clrscr();
   printf("How many numbers you want to enter in the array: ");
   scanf("%d",&num);
   printf("Please Enter Elements in Ascending order\n");
   for (i = 0; i < num; i++)
      scanf("%d",&arr[i]);
   printf("Enter the number which position you want to know: ");
   scanf("%d", &tar);
   f = 0;
   l = num - 1;
   mid = (f+l)/2;
   while (f <= l) {
      if (arr[mid] < tar)
                 f = mid + 1;
      else if (arr[mid] == tar) {
                 printf("%d is at %d position\n", tar, mid+1);
          break;
      }
      else
             l = mid - 1;
      mid = (f + l)/2;
   }
   if (f> l)
      printf("This element is not in the Array");
getch();
}

    Output: 

    How many numbers you want to enter in the array: 6
Please Enter Elements in Ascending order

12
23
34
45
56
67

Enter the number which position you want to know: 23

23 is at 2 position

    C Recursive Binary Search

    In recursive binary search, we will use the recursion of function: 

    #include <stdio.h>
#include<conio.h>
int BinarySearch(int arr[], int l, int r, int tar)
{
    int mid;
    if (r >= l) {
                mid = l + (r - l) / 2;
                if (arr[mid] == tar)
                    return mid;
    if (arr[mid] > tar)
                return BinarySearch(arr, l, mid - 1, tar)
    return BinarySearch(arr, mid + 1, r, tar);
    }
    return -1;
}
void main()
{
    int arr[100],i,res,num,tar;
    clrscr();
    printf("How many Elements you wan to enter in the array: ");
    scanf("%d",&num);
    printf("Enter Elements in the Ascending order\n");
    for(i=0;i<num;i++)
         scanf("%d",&arr[i]);
   printf("Enter the element which position you want to know: ");
   scanf("%d",&tar);
   res = BinarySearch(arr, 0, num - 1, tar);
   if(res == -1)
       printf("The element is not present in array");
   else
       printf("%d is at %d position", tar,res+1);
getch();
}

    Output: 

    How many Elements you want to enter in the array: 5
Enter Elements in Ascending order

12
224
35
46
68

Enter the element which position you want to know: 46

46 is at 4 position

    Conclusion

    In conclusion, the binary search algorithm dramatically reduces the number of comparisons required, which makes it exceptionally fast, even with vast amounts of data.

    Here in this tutorial, we mentioned the basics of the binary search algorithm, its advantages and disadvantages, and the code for binary search in C.

    Try out these codes, and we hope the information in this tutorial answers your queries regarding the topic.

    Good luck!

    People are also reading:

    Previous Tutorial Next Tutorial